﻿//
// Created by Freeman on 2022/1/19.
//

#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <ios>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include "../Headers/Simulation.h"
#include "../Headers/Util.h"

using namespace std;

void PAT_A1042::solve() {
    // 生成卡片名数组
    vector<string> cards(54), cardsCopy;
    string cardName_s = "S", cardName_h = "H", cardName_c = "C", cardName_d = "D", cardName_j = "J";
    for (int i = 1; i <= 13; i++) {
        cardsCopy.push_back(cardName_s + to_string(i));
    }
    for (int i = 1; i <= 13; i++) {
        cardsCopy.push_back(cardName_h + to_string(i));
    }
    for (int i = 1; i <= 13; i++) {
        cardsCopy.push_back(cardName_c + to_string(i));
    }
    for (int i = 1; i <= 13; i++) {
        cardsCopy.push_back(cardName_d + to_string(i));
    }
    for (int i = 1; i <= 2; i++) {
        cardsCopy.push_back(cardName_j + to_string(i));
    }

    // 读取顺序
    int repeat;
    cin >> repeat;
    vector<int> sequence;
    for (int i = 1; i <= 54; i++) {
        int tmp;
        cin >> tmp;
        sequence.push_back(tmp);
    }

    // shuffle
    for (int r = 1; r <= repeat; r++) {
        // cardsCopy中的卡片按照给定顺序转移到cards中
        for (int i = 0; i < 54; i++) {
            cards[sequence[i] - 1] = cardsCopy[i];
        }
        // cards赋值给cardsCopy
        for (int i = 0; i < 54; i++) {
            cardsCopy[i] = cards[i];
        }
    }

    // 输出
    for (int i = 0; i < 54; i++) {
        cout << cards[i];
        if (i < 53) cout << " ";
    }
}

void PAT_A1046::solve() {
    // 读入距离信息
    int nExits, tmp = 0, roundTripDist = 0;
    cin >> nExits;
    vector<int> dists; // dists[i]存储顺时针方向上节点1到i的距离
    for (int i = 1; i <= nExits; i++) {
        dists.push_back(roundTripDist); // 在第一次循环时推入0
        cin >> tmp;
        roundTripDist += tmp;
    }
    dists.insert(dists.begin(), tmp); // N->1的距离存入dists[0]（其实用不到）

    int repeat;
    cin >> repeat;
    for (int r = 1; r <= repeat; r++) {
        int src, dest;
        cin >> src >> dest;
        if (src > dest) {
            tmp = src;
            src = dest;
            dest = tmp;
        }
        int forward = dists[dest] - dists[src], backward = roundTripDist - forward;
        cout << (forward < backward ? forward : backward);
        if (r < repeat) cout << endl;
    }
}

void PAT_A1065::solve() {
    int repeat;
    cin >> repeat;
    for (int r = 1; r <= repeat; r++) {
        long long a, b, c;
        cin >> a >> b >> c;
        cout << "Case #" << r << ": ";
        cout << (judge(a, b, c) ? "true" : "false");
        if (r < repeat) cout << endl;
    }
}

bool PAT_A1065::judge(long long a, long long b, long long c) {
    long long sum = a + b;
    if (a == 0 || b == 0) return sum > c;
    else if (a > 0 && b > 0) {
        if (c <= 0) return true;
        else {
            if (sum < 0) return true; // 上溢出
            else return sum > c;
        }
    }
    else if (a < 0 && b < 0) {
        if (c >= 0) return false; // 下溢出时，结果可能为0，也可能大于0
        else {
            if (sum >= 0) return false; // 下溢出
            else return sum > c;
        }
    }
    else if ((a > 0 && b < 0) || (a < 0 && b > 0)) return sum > c; // a,b异号，必定不会越界
}

void PAT_A1002::solve() {
    // 接收输入并完成加法
    map<int, double> expCoMap; // 次数-系数映射
    for (int r = 1; r <= 2; r++) {
        int nItems;
        cin >> nItems;
        for (int i = 1; i <= nItems; i++) {
            int exponent;
            double coefficient;
            cin >> exponent >> coefficient;
            if (expCoMap.count(exponent)) {
                double origin = expCoMap.at(exponent);
                coefficient += origin;
                if (abs(coefficient) < 1e-8) expCoMap.erase(exponent); // 系数为0时予以移除
                else expCoMap.at(exponent) = coefficient;
            }
            else expCoMap.insert(pair<int, double>(exponent, coefficient));
        }
    }

    // 输出
    map<int, double>::reverse_iterator rit;
    // 设置输出格式。注意标准库在输出时向0舍入，在某些情况下表现会与四舍五入有所不同。
    cout << setiosflags(ios::fixed) << setprecision(1);
    cout << (expCoMap.size());
    for (rit = expCoMap.rbegin(); rit != expCoMap.rend(); rit++) {
        cout << " " << rit->first << " " << rit->second; // 这种写法可以避免对是否在结尾输出空格的讨论
    }
}

void PAT_A1009::solve() {
    auto coefficientVecA = new double[1001], coefficientVecB = new double[1001]; // 存储输入多项式
    auto coefficientVec = new double[2001]; // 存储输出多项式；乘积次数为0~2000
    for (int i = 0; i <= 1000; i++) {
        coefficientVec[i] = coefficientVecB[i] = coefficientVecA[i] = 0;
    }
    for (int i = 1001; i <= 2000; i++) coefficientVec[i] = 0;
    // 第一轮读入
    int nItems;
    cin >> nItems;
    for (int i = 1; i <= nItems; i++) {
        int exponent;
        double coefficient;
        cin >> exponent >> coefficient;
        coefficientVecA[exponent] += coefficient;
    }
    // 第二轮读入
    cin >> nItems;
    for (int i = 1; i <= nItems; i++) {
        int exponent;
        double coefficient;
        cin >> exponent >> coefficient;
        coefficientVecB[exponent] += coefficient;
    }

    // 计算乘积
    for (int i = 0; i <= 1000; i++) {
        for (int j = 0; j <= 1000; j++) {
            coefficientVec[i + j] += (coefficientVecA[i] * coefficientVecB[j]);
        }
    }
    // 统计非零项
    int count = 0;
    for (int i = 0; i <= 2000; i++) {
        if (abs(coefficientVec[i]) > 1e-8) count += 1;
    }
    // 输出
    cout << setiosflags(ios::fixed) << setprecision(1);
    cout << count;
    for (int i = 2000; i >= 0; i--) {
        if (abs(coefficientVec[i]) > 1e-8) cout << " " << i << " " << coefficientVec[i];
    }
}

void PAT_A1011::solve() {
    double maxOdds[3];
    string results[3];
    for (int i = 0; i <= 2; i++) {
        double odd;
        cin >> odd;
        maxOdds[i] = odd;
        results[i] = "W";
        cin >> odd;
        if (odd > maxOdds[i]) {
            maxOdds[i] = odd;
            results[i] = "T";
        }
        cin >> odd;
        if (odd > maxOdds[i]) {
            maxOdds[i] = odd;
            results[i] = "L";
        }
    }
    for (int i = 1; i <= 3; i++) {
        cout << results[i - 1] << " ";
    }
    cout << setiosflags(ios::fixed) << setprecision(2);
    cout << (maxOdds[0] * maxOdds[1] * maxOdds[2] * 0.65 - 1) * 2;
}

void PAT_A1006::solve() {
    int nRecord;
    cin >> nRecord;
    string fTimeIn, fTimeOut; // 暂存格式化时间
    string unlockID, lockID; // 解锁人和上锁人的ID
    int unlockTime, lockTime; // 解锁和上锁时间
    // 变量初始化
    cin >> unlockID >> fTimeIn >> fTimeOut;
    lockID = unlockID;
    unlockTime = formatted2Second(fTimeIn);
    lockTime = formatted2Second(fTimeOut);
    // 读取输入
    for (int r = 2; r <= nRecord; r++) {
        string ID;
        cin >> ID >> fTimeIn >> fTimeOut;
        if (formatted2Second(fTimeIn) < unlockTime) {
            unlockTime = formatted2Second(fTimeIn);
            unlockID = ID;
        }
        if (formatted2Second(fTimeOut) > lockTime) {
            lockTime = formatted2Second(fTimeOut);
            lockID = ID;
        }
    }
    cout << unlockID << " " << lockID;
}

int PAT_A1006::formatted2Second(string fTime) {
    vector<string> sectors = Util::strSplit(std::move(fTime), ':');
    return stoi(sectors[0]) * 3600 + stoi(sectors[1]) * 60 + stoi(sectors[2]);
}

void PAT_A1036::solve() {
    int nLines;
    cin >> nLines;
    int boyLowestScore = 101, girlHighestScore = -1;
    string boyLowestID, girlHighestID, boyLowestName, girlHighestName;
    for (int l = 1; l <= nLines; l++) {
        string tmpName, tmpGender, tmpID;
        int tmpScore;
        cin >> tmpName >> tmpGender >> tmpID >> tmpScore;
        switch (tmpGender.at(0)) {
        case 'M':
            if (tmpScore < boyLowestScore) {
                boyLowestScore = tmpScore;
                boyLowestID = tmpID;
                boyLowestName = tmpName;
            }
            break;
        case 'F':
            if (tmpScore > girlHighestScore) {
                girlHighestScore = tmpScore;
                girlHighestID = tmpID;
                girlHighestName = tmpName;
            }
            break;
        }
    }

    // 输出
    if (girlHighestID.length() == 0) cout << "Absent" << endl;
    else cout << girlHighestName << " " << girlHighestID << endl;
    if (boyLowestID.length() == 0) cout << "Absent" << endl;
    else cout << boyLowestName << " " << boyLowestID << endl;
    if (boyLowestID.length() == 0 || girlHighestID.length() == 0)cout << "NA" << endl;
    else cout << girlHighestScore - boyLowestScore << endl;
}

void PAT_A1031::solve() {
    string str;
    cin >> str;
    int N = str.length();
    int k = ceil(N / 3.0), n2 = N - k * 2 + 2;
    int nBlankSpace = n2 - 2;
    // 输出除最后一行外的前面各行
    for (int row = 1; row <= k - 1; row++) {
        cout << str.at(row - 1);
        for (int i = 1; i <= nBlankSpace; i++) cout << " ";
        cout << str.at(str.length() - row) << endl;
    }
    // 输出最后一行
    for (int i = k - 1; i <= str.length() - k; i++) cout << str.at(i);
}

void PAT_A1019::solve() {
    int deci, base;
    cin >> deci >> base;
    vector<int> v = Util::deci2AnyBase(deci, base);

    bool flag = true;
    for (int i = 0; i <= v.size() / 2; i++) {
        if (v[i] != v[v.size() - 1 - i]) {
            flag = false;
            break;
        }
    }
    cout << (flag ? "Yes" : "No") << endl;
    for (int i = 0; i <= v.size() - 1; i++) {
        cout << v[i];
        if (i < v.size() - 1) cout << " ";
    }
}

void PAT_A1027::solve() {
    int r, g, b;
    cin >> r >> g >> b;
    vector<int> rv = Util::deci2AnyBase(r, 13), gv = Util::deci2AnyBase(g, 13), bv = Util::deci2AnyBase(b, 13);
    vector<vector<int>> vectors;
    vectors.push_back(rv);
    vectors.push_back(gv);
    vectors.push_back(bv);
    for (int i = 0; i <= 2; i++) {
        vector<int>& v = vectors[i];
        if (v.size() < 2) { // 长度小于2时补0
            v.push_back(v[0]);
            v[0] = 0;
        }
    }

    cout << "#";
    for (int i = 0; i <= 2; i++) {
        vector<int>& v = vectors[i];
        for (int j = 0; j <= 1; j++) {
            if (v[j] >= 10) cout << (char)('A' + (v[j] - 10));
            else cout << v[j];
        }
    }
}

void PAT_A1058::solve() {
    // 接收输入，并转为整型向量
    string currencyA, currencyB;
    cin >> currencyA >> currencyB;
    vector<string> tmpVA = Util::strSplit(currencyA, '.'), tmpVB = Util::strSplit(currencyB, '.');
    vector<int> vA, vB;
    for (int i = 0; i <= 2; i++) {
        vA.push_back(stoi(tmpVA.at(i)));
        vB.push_back(stoi(tmpVB.at(i)));
    }

    // 计算A+B
    int knut = vA.at(2) + vB.at(2);
    int sickle = vA.at(1) + vB.at(1);
    int galleon = vA.at(0) + vB.at(0);
    if (knut >= 29) {
        knut -= 29;
        sickle += 1;
    }
    if (sickle >= 17) {
        sickle -= 17;
        galleon += 1;
    }
    cout << galleon << "." << sickle << "." << knut;
}

void PAT_A1061::solve() {
    string strA, strB, strC, strD;
    cin >> strA >> strB >> strC >> strD;
    string DAY;
    int HH = 0, MM = 0;
    // 解码DAY和HH
    int turn = 1;
    for (int i = 0; i < strA.length() && i < strB.length(); i++) {
        if (strA.at(i) == strB.at(i)) {
            char c = strA.at(i);
            if (turn == 1) { // DAY
                if (c < 'A' || c > 'G') continue; // 日期只可能是大写字母A~G（注意不是A~Z，下同）
                switch (c - 'A') {
                case 0:
                    DAY = "MON";
                    break;
                case 1:
                    DAY = "TUE";
                    break;
                case 2:
                    DAY = "WED";
                    break;
                case 3:
                    DAY = "THU";
                    break;
                case 4:
                    DAY = "FRI";
                    break;
                case 5:
                    DAY = "SAT";
                    break;
                case 6:
                    DAY = "SUN";
                    break;
                }
                turn += 1;
            }
            else { // HH
                if (c >= '0' && c <= '9') {
                    HH = c - '0';
                    break;
                }
                else if (c >= 'A' && c <= 'N') {
                    HH = 10 + c - 'A';
                    break;
                }
                else continue; // HH只可能是数字或大写字母A~N
            }
        }
    }
    // MM
    for (int i = 0; i < strC.length() && i < strD.length(); i++) {
        if (strC.at(i) == strD.at(i)) {
            char c = strC.at(i);
            if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) { // 分钟只能是字母
                MM = i;
                break;
            }
        }
    }

    cout << DAY << " ";
    cout << setw(2) << setfill('0') << HH << ":";
    cout << setw(2) << setfill('0') << MM;
}

void PAT_A1073::solve() {
    // 预处理
    string scientific;
    cin >> scientific;
    string number, exponent_str, out;
    vector<string> v = Util::strSplit(scientific, 'E');
    number = v.at(0);
    exponent_str = v.at(1);

    // 处理次数
    bool positive = number.at(0) == '+', expPositive = exponent_str.at(0) == '+';
    string::size_type nonZeroIndex = exponent_str.find_first_not_of('0', 1); // 系数中除符号外，首个非0字符的位置
    int exponent = 0;
    if (nonZeroIndex != string::npos) {
        string absoluteExp_str = exponent_str.substr(nonZeroIndex); // 系数绝对值的字符串形式
        exponent = stoi(absoluteExp_str) * (expPositive ? 1 : -1); // 系数
    }
    // 处理乘号左边的数
    cout << (positive ? "" : "-"); // 先输出符号
    number = number.substr(1); // 去除符号
    int nSignificant = number.length() - 1; // 显著数字位数
    if (exponent == 0) { // 系数为0，无需改动
    }
    else if (exponent < 0) { // 系数小于0，左侧补0
        int nZero = abs(exponent);
        number.erase(number.find('.'), 1); // 移除小数点
        number.insert(0, nZero, '0'); // 左侧补0
        number.insert(1, 1, '.'); // 恢复小数点
    }
    else { // 系数大于0，视情况右侧补0
        if (exponent >= nSignificant - 1) { // 需要补零（包含恰好去除小数点的情况）
            number.insert(number.length(), exponent - (nSignificant - 1), '0'); // 右侧补0
            number.erase(number.find('.'), 1);
        }
        else { // 仅移动小数点
            int dotIndex = number.find('.');
            number.erase(dotIndex, 1);
            dotIndex += exponent;
            number.insert(dotIndex, 1, '.');
        }
    }
    cout << number;
}

void PAT_A1001::solve() {
    int a, b;
    cin >> a >> b;
    int sum = a + b;
    string sumStr = to_string(sum);
    int count = 1; // 计数器，实现每三个数字加一个逗号
    for (int index = sumStr.length() - 1; index > (sum < 0 ? 1 : 0); index -= 1, count += 1) {
        if (count == 3) {
            count = 0;
            sumStr.insert(index, 1, ',');
        }
    }
    cout << sumStr;
}

void PAT_A1005::solve() {
    string str;
    cin >> str;
    // 求和
    int sum = 0;
    for (char c : str) {
        sum += (c - '0');
    }
    if (sum == 0) {
        cout << "zero";
        return;
    }
    // 存储各位数的英语表达
    vector<string> words;
    for (; sum > 0; sum /= 10) {
        int digit = sum % 10;
        switch (digit) {
        case 0:
            words.emplace_back("zero");
            break;
        case 1:
            words.emplace_back("one");
            break;
        case 2:
            words.emplace_back("two");
            break;
        case 3:
            words.emplace_back("three");
            break;
        case 4:
            words.emplace_back("four");
            break;
        case 5:
            words.emplace_back("five");
            break;
        case 6:
            words.emplace_back("six");
            break;
        case 7:
            words.emplace_back("seven");
            break;
        case 8:
            words.emplace_back("eight");
            break;
        case 9:
            words.emplace_back("nine");
            break;
        }
    }
    for (int i = words.size() - 1; i >= 0; i--) {
        cout << words.at(i);
        if (i > 0) cout << " ";
    }
}

void PAT_A1035::solve() {
    int n;
    cin >> n;
    vector<Info> v;
    // 读入
    for (int r = 1; r <= n; r++) {
        string userName;
        char pwd[11];
        cin >> userName >> pwd;
        v.emplace_back(userName, pwd);
    }
    // 处理
    int modifyCount = 0;
    for (Info& info : v) {
        for (int i = 0; info.pwd[i] != '\0'; i++) {
            if (info.pwd[i] == '1') {
                info.pwd[i] = '@';
                info.modified = true;
            }
            else if (info.pwd[i] == '0') {
                info.pwd[i] = '%';
                info.modified = true;
            }
            else if (info.pwd[i] == 'l') {
                info.pwd[i] = 'L';
                info.modified = true;
            }
            else if (info.pwd[i] == 'O') {
                info.pwd[i] = 'o';
                info.modified = true;
            }
        }
        if (info.modified) modifyCount += 1;
    }
    // 输出
    if (modifyCount == 0) {
        cout << "There " << (n > 1 ? "are " : "is ") << n << " account" << (n > 1 ? "s" : "")
            << " and no account is modified";
    }
    else {
        cout << modifyCount << endl;
        for (Info info : v) {
            if (info.modified) {
                cout << info.userName << " " << info.pwd;
                modifyCount -= 1;
                if (modifyCount > 0) cout << endl; // 最后一行后不加换行符
            }
        }
    }
}

void PAT_A1077::solve() {
    int nLines;
    cin >> nLines;
    getchar(); // 去除换行符
    vector<string> v;
    int maxLength = 0;
    for (int r = 1; r <= nLines; r++) {
        string tmp;
        getline(cin, tmp);
        if (tmp.length() > maxLength) maxLength = tmp.length();
        v.emplace_back(tmp);
    }

    // 寻找“口癖”
    string kuchiguse;
    bool complete = false;
    for (int i = 1; i <= maxLength; i++) {
        char c = v.at(0).at(v.at(0).length() - i);
        for (const string& str : v) {
            if (str.at(str.length() - i) != c) { // 倒数第i个字符不统一，退出循环
                complete = true;
                break;
            }
        }
        if (complete) break;
        kuchiguse.insert(0, 1, c);
    }
    cout << (kuchiguse.length() > 0 ? kuchiguse : "nai");
}

void PAT_A1082::solve() {
    string numStr;
    cin >> numStr;
    int num = stoi(numStr);
    if (num < 0) cout << "Fu ";
    if (numStr.at(0) == '-') numStr.erase(0, 1); // 去除负号，方便后续讨论
    if (numStr.length() == 9) { // 最高位为亿
        lessThan10k(numStr.substr(0, 1), false);
        cout << " Yi";
        if (numStr.find_first_not_of('0', 1) != string::npos || numStr.find_first_not_of('0', 5) != string::npos) cout << " "; // 后续仍有非0数字时，输出空格
        lessThan10k(numStr.substr(1, 4), true);
        cout << " Wan"; // TODO: 万节全0时，既不能输出多余的“ling”，也不能输出“wan”
        if (numStr.find_first_not_of('0', 5) != string::npos) cout << " ";
        lessThan10k(numStr.substr(5, 4), true);
    }
    else if (numStr.length() < 9 && numStr.length() > 4) { // 万以上
        int nHighDigits = numStr.length() - 4;
        lessThan10k(numStr.substr(0, nHighDigits), false);
        cout << " Wan";
        if (numStr.find_first_not_of('0', nHighDigits) != string::npos) cout << " ";
        lessThan10k(numStr.substr(nHighDigits, 4), true);
    }
    else { // 万以下
        lessThan10k(numStr, false);
    }
}

void PAT_A1082::lessThan10k(const string& str, bool hasHigher) {
    int num = stoi(str);
    bool unitValid; // 本次是否输出单位
    if (num == 0 && !hasHigher) {
        singleDigit('0'); // 传入为0，且没有更高级小节时，输出“ling”
        return;
    }
    for (int i = 0; i < str.length(); i++) {
        unitValid = false;
        int digit = str.at(i) - '0';
        singleDigit(digit + '0');
        if (i + 1 < str.size()) cout << " "; // 最后一个数字后不输出空格
        if (digit > 0) {
            unitValid = true;
            switch (str.size() - 1 - i) {
            case 3:
                cout << "Qian";
                break;
            case 2:
                cout << "Bai";
                break;
            case 1:
                cout << "Shi";
                break;
            }
        }
        if (str.find_first_not_of('0', i + 1) == string::npos) return; // 如果后面全为0，则无需再输出任何内容
        else {
            if (unitValid) cout << " "; // 该空格只能跟在单位后
        }
        if (digit == 0) {
            if (str.find_first_not_of('0', i + 1) == string::npos) return; // 后续数字全为0，退出循环
            else {
                i = str.find_first_not_of('0', i + 1) - 1; // 跳过连续的0
            }
        }
    }
}

void PAT_A1082::singleDigit(char digit) {
    switch (digit) {
    case '0':
        cout << "ling";
        break;
    case '1':
        cout << "yi";
        break;
    case '2':
        cout << "er";
        break;
    case '3':
        cout << "san";
        break;
    case '4':
        cout << "si";
        break;
    case '5':
        cout << "wu";
        break;
    case '6':
        cout << "liu";
        break;
    case '7':
        cout << "qi";
        break;
    case '8':
        cout << "ba";
        break;
    case '9':
        cout << "jiu";
        break;
    }
}
